package 二分.二分答案;

import org.junit.Test;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/6 16:24
 */
public class leetcode2554从一个范围选择最多的整数I {

    /*
    数据范围：
     1 <= banned.length <= 10 ^ 4
    1 <= banned[i], n <= 10 ^ 4
    1 <= maxSum <= 10 ^ 9
     */
    public static int solution(int ban[],int n,int maxSum){
        int sum = 0, count = 0;
        Set<Integer> set = new HashSet<>();
        for(int num : ban){
            set.add(num);
        }
        /*
         其实 可以 用二分
         但是 上面的 遍历 已经 O(N) 了
         所以 改变不了 时间 复杂度的所以
         直接 遍历 就行
         */
        for(int  i = 1;i <= n;i++){
            // 这里的 判断 的 技巧 写的 很漂亮, sum + i <= maxSum
            // 这样写 是 最简洁的 , **提前判断!**
            if(!set.contains(i) && sum + i <= maxSum){
                sum += i;
                count++;
            }
        }
        return count;
    }



    /*
        加强了 数据 范围 之后, 这道题
        就是 一个 标准的 二分 答案的题目
     */




    /*
         数据范围：
     1 <= banned.length <= 10 ^ 4
    1 <= banned[i]<= 10 ^ 9
     1 <= n <= 10 ^ 18
    1 <= maxSum <= 10 ^ 18
    如果 是 这样的 一个 数据范围的 话, 那么 上面的 方法 就不对 了!
    得用二分了!
     */
    // 1 ~ n 求和 的 最快 方式 高斯算法  (1 + n) * n / 2
    // 再减去 sum(ban[]) 但是 这样 等价于 maxSum + sum(ban[])
    //所以我们 可以 对 n 进行二分


    /*
     下面 这是个 错误的 版本
     */
    public long solution(int ban[],long n,long maxSum){
//        long count = 0;
        long sumBan = 0, sumN = 0;
        Set<Integer> set = new HashSet<>(ban.length); // 减少扩容消耗
        for(int num : ban){
            if(!set.contains(num)){
                sumBan +=num;
                /*
                 如果 当前 值 比 n 大 ,就 取不到, 没必要 进行记录
                 */
                set.add(num);
            }
        }
        // 相对论, a + b = c ,则 a = c - b
        maxSum += sumBan;
        long l = 1,r = n;
        while(l < r){
            long mid = l + r  + 1>> 1;
            sumN = (mid + 1) * mid >> 1;
            if(sumN > maxSum){
                r = mid - 1;
            }
            else{
                l = mid;
            }
        }
        int count = 0;
        for(int number : set){
            if(number <= l){
                count++;
            }
        }
        return l - count;
    }



    public static int solution1(int[] ban, int n, int maxSum){
//        TreeSet<Integer> set = new TreeSet<>();
        Set<Integer> set = new HashSet<>();
        for(int num : ban){
            if(num <= n){
                set.add(num);
            }
        }
        Integer[] filter = set.toArray(new Integer[set.size()]);
        // 排序
        Arrays.sort(filter);
        // 求 前缀和
        int [] preSum = new int[ban.length + 1];
        for(int i = 0;i < filter.length;i++){
            preSum[i + 1] = preSum[i] + filter[i];
        }
        int l = 1, r =  n;
        while(l < r){
            int mid = l + r + 1>> 1;
            int index = check2(mid, filter);
            // 1 ~ mid 的和 减去 filter 数组中的 和
            if ((mid + 1) * mid / 2 - preSum[index + 1] > maxSum){
                r = mid - 1;
            }
            else{
                l = mid;
            }
        }
//        int check = check2(l,filter);
        return filter.length == 0 ? l : l - check2(l,filter) - 1;
    }
    /*
      这个 函数 什么 意思 呢 ：
      这个 函数的 返回 值 : 1 ~ mid 之间 不在 filter 数组 中 的 元素的 和:
       也就是 求 ：  1 ~ mid 之间 不在 filter 数组 中 的 元素的 和:
       这是单独 的 一个问题，
       怎么 算 时间复杂度 最低 ？
       ① : 暴力枚举

       ②： 排序 ， 二分
     */


    /*
         这里 采用 最暴力的额写法
         @return: arr[0] ：<= mid 的和   arr[1]: 表示 <= mid 的 元素 个数
     */
    private static int[] check(int mid, Integer[] filter) {
        int sum = 0,count = 0;
        for(int num : filter){
                if(num <= mid){
                    sum += num;
                    count++;
                }
            }
        return new int[]{(mid + 1) * mid / 2 - sum,count};
    }


    /*
     将 filter 排序 ,便于 二分
     返回 一个 下标 index 表示 <= mid 的一个 最右边的 下标
     再求一个前缀和 ,preSum ,能在 O(1) 的时间内 求出 filter 数组中 [0,index] 的 和
     最完美的 解决方案 !
     */
    public static int check2(int mid,Integer[] filter){
        int l = 0,r = filter.length - 1;
        while(l < r){
            int mid2 = l + r + 1 >> 1;
            if(filter[mid2] > mid){
                r = mid2 - 1;
            }
            else{
                l = mid2;
            }
        }
        return l;
    }

    /*
     要注意 下面 这个  case
     导致 filter [] 数组 直接 没有元素的 情况!
     */
    public static void main(String[] args) {
//        int ban[] = {1,6,5};
        int ban[] = {11};
        int n = 7 ,max = 50;
//        System.out.println(solution(ban,n,max));
        System.out.println(solution1(ban,n,max));
        System.out.println((Long.MAX_VALUE + "").length());
        System.out.println(Long.MAX_VALUE > (long)(10 ^ 18));
    }


}
